package class_3;


import java.io.IOException;
import java.util.Arrays;
import java.util.Random;
public class Coding_DecodeWays {
	public static int numDecodings(String s) {
		return f(s.toCharArray(), 0);
	}
	
	public static int f(char[] s, int cur) {
		if(cur==s.length) {
			return 1;//为什么返回1？
		}
		int ans;
		if(s[cur]=='0') {
			ans = 0;
		}
		else {
			ans = f(s,cur+1);
			if(cur+1<s.length && (s[cur]-'0')*10 + (s[cur+1] - '0') <= 26) {
				ans += f(s,cur+2);
			}
		}
		return ans;
	}
	
	public static int numDecodings1(String s) {
		if(s==null || s.length() < 1) {
			return 0;
		}
        int[] dp = new int[s.length()];
        Arrays.fill(dp, -1); // 初始化dp数组，表示尚未计算的部分
        return f1(s.toCharArray(), 0, dp); // 调用递归辅助方法
    }

    public static int f1(char[] s, int cur, int[] dp) {
        // 基准条件：如果已经处理到字符串末尾，则说明找到了一种有效解码方式
        if (cur == s.length) {
            return 1;
        }

        // 如果该位置已经计算过解码方案数，直接返回缓存结果
        if (dp[cur] != -1) {
            return dp[cur];
        }

        // 初始化答案
        int ans;
        
        // 如果当前字符是'0'，不能单独解码，直接返回0
        if (s[cur] == '0') {
            ans = 0;
        } else {
            // 尝试解码当前单个字符
            ans = f1(s, cur + 1, dp);
            
            // 尝试解码当前和下一个字符组合
            if (cur + 1 < s.length && (s[cur] - '0') * 10 + (s[cur + 1] - '0') <= 26) {
                ans += f1(s, cur + 2, dp);
            }
        }

        // 保存结果到dp数组中
        dp[cur] = ans;
        return ans;
    }
	public static int MAX = 100;
	public static char[] ch = new char[MAX];
	public static void main(String[] args) throws IOException {
		Random random = new Random();
		int n = random.nextInt(MAX);
		for(int i=0;i<n;i++) {
			ch[i] = (char)(random.nextInt(10) + '0');
		}
		String s = new String(ch,0,n);
	     System.out.println("字符串长度: " + n);
		 // 为了避免打印过长的字符串，截断显示部分内容
        if (n > 50) {
            System.out.println("字符串: " + s.substring(0, 50) + "...");
        } else {
            System.out.println("字符串: " + s);
        }

        // 暴力递归方式计算解码方案
        long start = System.nanoTime();
        int ret = numDecodings(s);
        long end = System.nanoTime();
        System.out.println("解码方案数 (暴力递归): " + ret);
        System.out.println("暴力递归耗时: " + (end - start) + " 纳秒");

        // 动态规划方式计算解码方案
        start = System.nanoTime();
        ret = numDecodings1(s);
        end = System.nanoTime();
        System.out.println("解码方案数 (动态规划): " + ret);
        System.out.println("动态规划耗时: " + (end - start) + " 纳秒");
        System.out.println("-----------------");
		
		
	}
}
